package sort.heapSort;

/**
 * @Author: zhang
 * @Description:
 * @Date: Created in 22:34 2019/9/20
 */
public class TopK {
    public static void main(String[] args) {
        int[] arrays = new int[]{5, 1, 7, 4, 8, 9, 2, 3, 6, 0,20,21,22,23,24,25};
        int k = 10;
        topK(arrays,k);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + " ");
        }
    }

    public static void topK(int[] a, int k) {
        for (int i = (k - 1) / 2; i >= 0; i--) {
            adjust(a, i, k-1);
        }
        for (int j = k + 1; j < a.length - 1; j++){
            if (a[0] < a[k + 1]) {
                a[0] = a[k + 1];
                adjust(a,0,k-1);
            }
        }
    }

    public static void adjust(int[] a, int start, int end) {
        int tmp = a[start];
        for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {
            //找到左右孩子的最小值下标
            if (i < end && a[i] > a[i + 1]) {
                i++;    //此时i的位置就是左右孩子的最大值
            }
            //比较tmp与左右孩子最小值
            if (a[i] < tmp) {
                a[start] = a[i];
                start = i;
            } else {
                //从后向前调整，发现小于tmp没有必要调整
                break;
            }
        }
        //退出循环以后把tmp放入
        a[start] = tmp;
    }
}
